package com.gitee.feizns.explore.data_structure.linked_list.singly.sort;

import com.gitee.feizns.explore.data_structure.linked_list.singly.ListNode;

/**
 * @author feizns
 * @since 2020/3/3
 */
public class SortList2 {

    private static ListNode create() {
        ListNode r = new ListNode(5);
        r.next = new ListNode(4);
        r.next.next = new ListNode(3);
        r.next.next.next = new ListNode(2);
        r.next.next.next.next = new ListNode(1);
        return r;
    }

    private static void println(ListNode n) {
        ListNode t = n;
        while ( t != null ) {
            System.out.print(t.val);
            t = t.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ListNode node = new SortList2().sortList(create());
        println(node);
    }

    public ListNode sortList(ListNode head) {
        if ( head == null || head.next == null )
            return head;
        ListNode prev = new ListNode(-1);
        prev.next = head;
        ListNode fast = prev;
        ListNode slow = fast;
        while ( fast.next != null && fast.next.next != null ) {
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = slow.next;
        slow.next = null;
        prev.next = sortList(prev.next);
        ListNode n2 = sortList(fast);
        prev.next = merge(prev.next, n2);
        return prev.next;
    }

    private static ListNode merge(ListNode l, ListNode r) {
        if ( l == null )
            return r;
        else if ( r == null )
            return l;
        else if ( l.val < r.val ) {
            l.next = merge(l.next, r);
            return l;
        } else {
            r.next = merge(r.next, l);
            return r;
        }
    }

}
